package com.cet.algorithm.数组;

import java.util.Arrays;

/**
 * @program: cet-practice
 * @description: 快排
 * @author: 陈恩涛
 * @create: 2023-05-05 08:41
 **/
public class QuickSort {

//    public static int partition(int[] array, int low, int high) {
//
//        // 取第一个元素为中心元素
//        int v = array[low];
//
//        //左右扫描指针
//        int left = low ;
//        int right = high + 1;
//
//        while (true) {
//            while (array[++left] < v) {
//                if (left == high) {
//                    break;
//                }
//            }
//            while (array[--right] > v) {
//                if (right == low) {
//                    break;
//                }
//            }
//            if (left >= right) {
//                break;
//            }
//            int temp = array[left];
//            array[left] = array[right];
//            array[right] = temp;
//        }
//        int temp = array[right];
//        array[right] = array[low];
//        array[low] = temp;
//        System.out.println(Arrays.toString(array));
//        return right;
//    }

    public static int partition(int[] array, int low, int high) {

        // 快慢指针法
        // 慢指针之前的以及当前位置的元素都小于pivot
        // 快指针对区域内元素进行扫描
        int slowIndex = low;
        int pivot = array[low];
        for (int i = low + 1; i <= high; i++) {
            if (array[i] < pivot) {
                slowIndex++;
                swap(array, slowIndex, i);
            }
        }

        swap(array, low, slowIndex);
        return slowIndex;
    }

    private static void swap(int[] array, int idx1, int idx2) {
        int temp = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = temp;
    }

    public static void quickSort(int[] array, int low, int high) {
        if (low >=  high) {
            return;
        }
        // 获取划分子数组的位置
        int position = partition(array, low, high);
        // 左子数组递归调用
        quickSort(array, low, position -1);
        // 右子数组递归调用
        quickSort(array, position + 1, high);
    }

    public static void main(String[] args) {
        int[] array = {6,72,113,11,23};
        quickSort(array, 0, array.length -1);
        System.out.println("排序后的结果");
        System.out.println(Arrays.toString(array));
    }
}
